package com.rui.study.algorithm.SORT_1_冒泡排序;

/**
 * @program: study_20180903
 * @description:
 * @author: Yaowr
 * @create: 2018-10-25 14:27
 **/
public class BubbleSort {

    /**
     * 冒泡排序：每次冒泡比较相邻两个元素，根据大小关系要求交换元素位置，一次冒泡至少有一个元素移动到他应该在的位置。
     * 最好时间复杂度：O(n) ，数据已经有序的情况下
     * 最坏时间复杂度：O(n²)，数据正好是逆序情况下
     * 空间复杂度：O(1)，即原地排序
     * 稳定性：稳定
     * @param a
     */
    public int bubbleSort(int[] a) {
        // 冒泡次数
        int i = 0;
        for (; i < a.length-1; i++) {
            boolean exchanged = false;
            // 两两比较，较大者往右移
            for (int j = 0; j+1 < a.length-i; j++) {
                if (a[j] > a[j+1]) {
                    exchanged = true;
                    // 左边大，则交换位置
                    a[j] += a[j+1];
                    a[j+1] = a[j] - a[j+1];
                    a[j] -= a[j+1];
                }
            }
            if (!exchanged) {
                break;
            }
        }
        return i;
    }

}
